CS424 Assignment 6

A general note: in order to make it easier for us to run your programs, please submit each program as a separate file that is directly executable. Put any non-executable text in comments.

Another general note: it turns out that it can be a bit tricky to define functions (like delay()) such that you can eachWorker or eachElem the function philosopher(), and have philosopher() invoke delay(). There are several ways to do this, but the simplest is the following: Put the definitions for philosopher() and delay() and any other methods that philosopher() uses directly or indirectly as top-level definitions in another file, e.g. philaux.py. Then, in your main file, import that file. Here is sample code showing what I mean:

philo.py:

import philaux
from nws.sleigh import Sleigh

s=Sleigh(verbose=True)
s.eachWorker(philaux.philosopher)

philaux.py:

import time, random

def delay():
  time.sleep(random.random())

def think():
  delay()

def philosopher():
  f=open('log', 'w')
  while True:
    f.write('thinking')
    f.flush()
    think()

1. Dining philosophers is a classic computer science synchronization problem. Picture K philosophers seated at a round table. Each thinks for a bit, then gets hungry and wants to eat. In order to eat, he needs two chopsticks. There are K total chopsticks, one located between each pair of philosophers. A particular chopstick can (obviously) only be used by one philosopher at a time.

   Here is psuedocode describing what they do:

   forever {
     think()
     grab(left chopstick)
     delay()
     grab(right chopstick)
     eat()
     replace(left chopstick)
     delay()
     replace(right chopstick)
   }
   

   1. Write a NWS program that implements this algorithm for K philosophers. Use eachWorker() to create the K workers. The delay() routine should sleep for a small, random period of a few seconds, using time.sleep() and random.random(). Write the think() and eat() routines to simulate time passing by using delay() internally. Run it with 4 philosophers. If you've done everything "correctly", your program should deadlock eventually, which you can see via the web interface. Why does this happen?
   2. Now, fix your program, ideally without adding any additional synchronization.
2. Matrix multiplication is similar to the DNA example that we explored in class, but simpler since there are no inter-task dependencies. As you know, multiplying a pxq matrix A and a qxr matrix B results in a pxr matrix C. Write a result-parallel version of matrix multiplication, where each element of C is a separate task evaluated via eachElem. Assume that each element of A and B are stored in NetWorkSpaces individually.

   You can store A(i,j) like this:

   ws.store('A_%d_%d' % (i, j), a[i][j])
   

   Run your program on a reasonable sized matrix and 1,2, and 4 processors and report the performance.

3. Now write a more efficient matrix multiplication that uses blocks rather than individual elements. Each block of A and B will be stored as one value in NWS, and each task will calculate one block of C. Run your program on 1,2, and 4 processors and compare its performance to the previous version.